package 剑指Offer.困难;

import java.util.Arrays;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/10/24 10:37
 */
public class _51数组中的逆序对 {

    public static void main(String[] args) {
        _51数组中的逆序对 a = new _51数组中的逆序对();
        a.reversePairs(new int[]{1,2,3,5});
    }
    

    int[] nums, tmp;
    
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);

    }

    private int mergeSort(int l, int r) {
        if (l >= r) {
            return 0;
        }
        int m = (l + r) / 2;
        // 左右划分
        int res = mergeSort(l, m) + mergeSort(m + 1, r);

        // 合并的阶段 可判断逆序对
        // i左边数组第一个下标 j右边数组第一个下标
        int i = l, j = m + 1;
        // 将 l到r 的所有元素加入的临时数组中
        for (int k = l ; k <= r; k++) {
            tmp[k] = nums[k];
        }
        for (int k = l; k <= r; k++) {
            // 左边数组已经到最后 
            if (i == m + 1) {
                nums[k] = tmp[j++];
            }
            // 右边数组的元素大于左边数组元素 或右边数组到最后
            else if (j == r + 1 || tmp[i] <= tmp[j] ) {
                nums[k] = tmp[i++];
            } else {
                // 左边大于右边 
                nums[k] = tmp[j++];
                // 统计逆序对
                res += m - i + 1;
            }
        }
        return res;
    }

}
